// 给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

// 示例:

// 输入:
// [
//   ["1","0","1","0","0"],
//   ["1","0","1","1","1"],
//   ["1","1","1","1","1"],
//   ["1","0","0","1","0"]
// ]
// 输出: 6

#include <vector>
#include <algorithm>
#include <stack>

using std::stack;
using std::max;
using std::vector;

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        int res{0};
        int m = matrix.size();
        if (m == 0) return 0;
        int n = matrix[0].size();
        vector<int> height(n);
        for (int i{0}; i < m; ++i) {
            // 一行一行的处理，每一行都要叠加上一行的高度
            for (int j{0}; j < n; ++j) {
                height[j] = (matrix[i][j] == '0' ? 0 : (1 + height[j]));
            }
            res = max(res, largestRectangleArea(height));
        }
        return res;
    }
    // LeetCode_84
    int largestRectangleArea(vector<int>& height) {
        int res{0};
        stack<int> s{};
        height.push_back(0);
        int n = height.size();
        for (int i{0}; i < n; ++i) {
            if (s.empty() || height[s.top()] <= height[i]) s.push(i);
            else {
                int tmp = s.top();
                s.pop();
                res = max(res, height[tmp] * (s.empty() ? i : (i - s.top()  - 1)));
                --i;
            }
        }
        return res;
    }
};

